<head>
    <meta charset="UTF-8">
<title>算法训练 Sereja and Squares</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】</p>
<div>Sereja在平面上画了n个点，点i在坐标(i,0)。然后，Sereja给每个点标上了一个小写或大写英文字母。Sereja不喜欢字母&quot;x&quot;，所以他不用它标记点。Sereja认为这些点是漂亮的，当且仅当：</div>
<div>&middot;所有的点可以被分成若干对，使得每个点恰好属于一一对之中。</div>
<div>&middot;在每对点中，横坐标较小的会被标上小写字母，较大的会被标上对应的大写字母。</div>
<div>&middot;如果我们在每对点上画一个正方形，其中已知的一对点会作为正方形的相对的顶点，它们间的线段会成为正方形的对角线，那么在所有画出的正方形中不会有相交或触碰的情况。</div>
<div>小Petya擦掉了一些小写字母和所有大写字母，现在Sereja想知道有多少种方法来还原每个点上的字母，使得还原后这些点是漂亮的。</div>
<p>【输入格式】</p>
<div>第一行是一个整数n，表示点的个数。</div>
<div>第二行是一个长度为n的字符串，包含小写字母和问号&quot;?&quot;，是按照横坐标递增的顺序的每个点的描述。问号表示这个点的字母被Petya擦掉了。保证输入串不含字母&quot;x&quot;。</div>
<p>【输出格式】<br />
输出答案对4294967296取模的值。如果没有可行的方案，输出0。<br />
【样例输入1】</p>
<div>4</div>
<div>a???</div>
<p>【样例输出1】<br />
50<br />
【样例输入2】</p>
<div>
<div>4</div>
<div>abc?</div>
</div>
<p>【样例输出2】<br />
0<br />
【样例输入3】</p>
<div>
<div>6</div>
<div>abc???</div>
</div>
<p>【样例输出3】<br />
1<br />
【数据规模和约定】</p>
<div>20个测试点的n分别为：</div>
<div>5,10,20,50,100,</div>
<div>200,500,1000,2000,5000,</div>
<div>10000,20000,30000,40000,50000,</div>
<div>60000,70000,80000,90000,100000.</div>